package cn.javadog.algorithm.m1_100;


import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

/**
 * 无重复字符的最长子串
 * https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
 * @author Sprite
 */
public class Algorithm3_2 {
	public static void main(String[] args) {
		System.out.println(lengthOfLongestSubstring("abcabcbb"));
		System.out.println(lengthOfLongestSubstring("bbbbb"));
		System.out.println(lengthOfLongestSubstring("pwwkew"));
		System.out.println(lengthOfLongestSubstring("au"));
		System.out.println(lengthOfLongestSubstring("aau"));
	}

	/**
	 * 双滑块，不固定窗口，最大满足条件
	 * 1、左侧开划，双指针
	 * 2、划过的元素计入一个treeset，查找的复杂度为 O(1)
	 * 3、右侧滑块滑到与左侧一致时，左侧滑块往后滑动，对比此时的窗口大小与历史最大窗口大小
	 */
	public static int lengthOfLongestSubstring(String s) {

		char[] chars = s.toCharArray();
		// 记录坐标
		int[] charDic = new int[128];
		Arrays.fill(charDic, -1);
		int left = 0, right = 0, maxLen = 0;

		while (right < chars.length) {
			// map 并不会清除 left 之前的key， 因此需要判断
			if (charDic[chars[right]] >= left) {
				// 将左滑块滑到指定位置
				left = charDic[chars[right]] + 1;
			}else {
				// 记录下大小
				maxLen = Math.max(maxLen, right - left + 1);
			}
			charDic[chars[right]] = right;
			right++;
		}
		return maxLen;
	}

	public static int lengthOfLongestSubstring2(String s) {
		// 记录字符上一次出现的位置
		int[] last = new int[128];
		for(int i = 0; i < 128; i++) {
			last[i] = -1;
		}
		int res=0;
		int start=0;
		for(int i=0;i<s.length();i++) {
			int index=s.charAt(i);
			start=Math.max(start,last[index]+1);
			res=Math.max(res,i-start+1);
			last[index]=i;
		}
		return res;
	}
}
